package leetCode.offer37;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 *
 */
public class Codec2 implements Codec{


    @Override
    public String serialize(TreeNode root) {
        if(root==null) return null;
        if(root.right==null&&root.left==null) return root.val+"";
        return levelOrder(root);
    }

    /**
     * 优化过的解法，通过
     * @param data
     * @return
     */
    @Override
    public TreeNode deserialize(String data) {
        if(data==null) return null;
        if(!data.contains("&")) new TreeNode(Integer.parseInt(data));
        String[] level = data.split("&");
        List<List<TreeNode>> array = new ArrayList<>();
        for(String str:level) {
            List<TreeNode> item = new ArrayList<>();
            String[] nums = str.split("\\|");
            for(String num:nums){
                if(num.equals("null")){
                    item.add(null);
                }else item.add(new TreeNode(Integer.parseInt(num)));
            }
            array.add(item);
        }
        for(int i=0;i<array.size()-1;i++){
            List<TreeNode> first = array.get(i);
            List<TreeNode> second = array.get(i+1);
            int index = 0;
            for (TreeNode treeNode : first) {
                if (treeNode != null) {
                    treeNode.left = second.get(index * 2);
                    treeNode.right = second.get(index * 2 + 1);
                    index++;
                }
            }
        }
        return array.get(0).get(0);
    }

    /**
     * 层次遍历
     * @param root
     * @return
     */
    public String levelOrder(TreeNode root) {
        Queue<TreeNode> queue= new LinkedList<>();
        StringBuilder result = new StringBuilder();
        if(root!=null) queue.add(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i=0;i<size;i++) {
                TreeNode node = queue.poll();
                if(node==null){
                    result.append("null");
                }
                else {
                    result.append(node.val);
                    queue.add(node.left);
                    queue.add(node.right);
                }
                result.append("|");
            }
            result.replace(result.length()-1,result.length(),"&");
        }
        result.replace(result.length()-1,result.length(),"");
        return result.toString();
    }

    public static void main(String[] args) {
        Codec codec = new Codec2();
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.right.left = new TreeNode(4);
        root.right.right = new TreeNode(5);
        System.out.println(codec.serialize(root));
        TreeNode node = codec.deserialize(codec.serialize(root));
        System.out.println("完成！！");

    }
}
